package com.atwyh;

import java.util.*;

/**
 * @Author wyh
 * @Date 2025/4/20 19:11
 * @description:
 */
class Solution {
    // 704
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle - 1;
            }
        }
        return -1;
    }

    // 27
    public int removeElement1(int[] nums, int val) {
        int size = nums.length;
        for (int i = 0; i < size; i++) {
            if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
                for (int j = i + 1; j < size; j++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;
    }

    // 27 双指针，快慢指针
    public int removeElement2(int[] nums, int val) {
        int fast, slow = 0;
        for (fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }

    // 977 冒泡排序
    public int[] sortedSquares1(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            nums[i] *= nums[i];
        }
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
        return nums;
    }

    public int[] sortedSquares2(int[] nums) {
        // 定义新数组
        int[] result = new int[nums.length];
        int left = 0;
        int right = nums.length - 1;
        int size = nums.length - 1;
        for (; left <= right; ) {
            if (nums[left] * nums[left] < nums[right] * nums[right]) {
                result[size--] = nums[right] * nums[right];
                right--;
            } else {
                result[size--] = nums[left] * nums[left];
                left++;
            }
        }
        return result;
    }

    //209 两个for循环
    // 暴力求解：一个决定滑动窗口的起点，一个决定滑动窗口的终点
    // result判断最短长度，初始化为最大值
    // 时间复杂度：O(n^2)
    // 空间复杂度：O(1)
    public int minSubArrayLen(int s, int[] nums) {
        int result = Integer.MAX_VALUE; // 最终的结果，初始化为最大值
        int sum = 0;                   // 子数组的数值之和
        int subLength = 0;             // 子数组的长度

        // 外层循环：遍历子数组起点 i
        for (int i = 0; i < nums.length; i++) {
            sum = 0; // 每次重新计算子数组的和
            // 内层循环：遍历子数组终点 j
            for (int j = i; j < nums.length; j++) {
                sum += nums[j]; // 累加当前子数组的和
                if (sum >= s) { // 如果子数组的和大于等于 s
                    subLength = j - i + 1; // 计算子数组的长度
                    result = Math.min(result, subLength); // 更新最短长度
                    break; // 找到符合条件的子数组后，跳出内层循环
                }
            }
        }

        // 如果 result 没有被更新，说明没有符合条件的子数组，返回 0
        return result == Integer.MAX_VALUE ? 0 : result;
    }

    // 209 双指针滑动窗口
    // result判断最短长度，初始化为最大值
    public int minSubArrayLen2(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }

    // 904 双指针滑动窗口
    public int totalFruit(int[] fruits) {
        int left = 0;
        Map<Integer, Integer> map = new HashMap<>();
        int result = 0;
        for (int right = 0; right < fruits.length; right++) {
            map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);
            while (map.size() > 2) {
                if (map.get(fruits[left]) == 1) {
                    map.remove(fruits[left]);
                } else {
                    map.put(fruits[left], map.get(fruits[left]) - 1);
                }
                left++;
            }
            result = Math.max(result, right - left + 1);
        }
        return result;
    }

    public int totalFruit2(int[] fruits) {
        int n = fruits.length;
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();

        int left = 0, ans = 0;
        for (int right = 0; right < n; ++right) {
            cnt.put(fruits[right], cnt.getOrDefault(fruits[right], 0) + 1);
            while (cnt.size() > 2) {
                cnt.put(fruits[left], cnt.get(fruits[left]) - 1);
                if (cnt.get(fruits[left]) == 0) {
                    cnt.remove(fruits[left]);
                }
                ++left;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }

    // 76. 最小覆盖子串

    // 原始目标字符计数
    Map<Character, Integer> targetCharCount = new HashMap<>();
    // 当前窗口中的字符计数
    Map<Character, Integer> windowCharCount = new HashMap<>();
    public String minWindow(String source, String target) {
        int targetLength = target.length();
        // 初始化目标字符计数
        for (int i = 0; i < targetLength; i++) {
            char currentChar = target.charAt(i);
            targetCharCount.put(currentChar, targetCharCount.getOrDefault(currentChar, 0) + 1);
        }
        int left = 0, right = -1; // 窗口左右边界
        int minLength = Integer.MAX_VALUE; // 最小窗口长度
        int startOfMinWindow = -1; // 最小窗口的起始位置
        int endOfMinWindow = -1; // 最小窗口的结束位置
        int sourceLength = source.length();
        // 滑动窗口主循环
        while (right < sourceLength) {
            ++right; // 扩展右边界
            if (right < sourceLength && targetCharCount.containsKey(source.charAt(right))) {
                windowCharCount.put(source.charAt(right), windowCharCount.getOrDefault(source.charAt(right), 0) + 1);
            }
            // 如果当前窗口满足条件，尝试收缩左边界
            while (isWindowValid() && left <= right) {
                // 更新最小窗口信息
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    startOfMinWindow = left;
                    endOfMinWindow = left + minLength;
                }
                // 收缩左边界
                if (targetCharCount.containsKey(source.charAt(left))) {
                    windowCharCount.put(source.charAt(left), windowCharCount.getOrDefault(source.charAt(left), 0) - 1);
                }
                ++left;
            }
        }
        // 返回结果
        return startOfMinWindow == -1 ? "" : source.substring(startOfMinWindow, endOfMinWindow);
    }
    // 检查当前窗口是否满足条件
    public boolean isWindowValid() {
        Iterator<Map.Entry<Character, Integer>> iterator = targetCharCount.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> entry = iterator.next();
            char key = entry.getKey();
            int requiredCount = entry.getValue();
            int currentCount = windowCharCount.getOrDefault(key, 0);
            if (currentCount < requiredCount) {
                return false; // 当前窗口不满足条件
            }
        }
        return true; // 当前窗口满足条件
    }

    // 方法二：优化  https://leetcode.cn/problems/minimum-window-substring/solutions/2713911/liang-chong-fang-fa-cong-o52mn-dao-omnfu-3ezz/
    public String minWindow2(String S, String t) {
        char[] s = S.toCharArray();
        int m = s.length;
        int ansLeft = -1;
        int ansRight = m;
        int[] cnt = new int[128];
        int less = 0;
        for (char c : t.toCharArray()) {
            if (cnt[c] == 0) {
                less++; // 有 less 种字母的出现次数 < t 中的字母出现次数
            }
            cnt[c]++;
        }

        int left = 0;
        for (int right = 0; right < m; right++) { // 移动子串右端点
            char c = s[right]; // 右端点字母
            cnt[c]--; // 右端点字母移入子串
            if (cnt[c] == 0) {
                // 原来窗口内 c 的出现次数比 t 的少，现在一样多
                less--;
            }
            while (less == 0) { // 涵盖：所有字母的出现次数都是 >=
                if (right - left < ansRight - ansLeft) { // 找到更短的子串
                    ansLeft = left; // 记录此时的左右端点
                    ansRight = right;
                }
                char x = s[left]; // 左端点字母
                if (cnt[x] == 0) {
                    // x 移出窗口之前，检查出现次数，
                    // 如果窗口内 x 的出现次数和 t 一样，
                    // 那么 x 移出窗口后，窗口内 x 的出现次数比 t 的少
                    less++;
                }
                cnt[x]++; // 左端点字母移出子串
                left++;
            }
        }
        return ansLeft < 0 ? "" : S.substring(ansLeft, ansRight + 1);
    }

    // 测试 entrySet() 方法
    public static void main1(String[] args) {
        // 创建一个 Map
        Map<String, Integer> map = new HashMap<>();
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        System.out.println("entries:" + entries);

        // 使用 entrySet() 遍历 Map
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();   // 获取键
            Integer value = entry.getValue(); // 获取值
            System.out.println("Key: " + key + ", Value: " + value);
        }
    }

    // 59
    public static int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0;  // 每一圈的起始点
        int offset = 1;
        int count = 1;  // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // j 代表列, i 代表行;

        while (loop <= n / 2) {

            // 顶部
            // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列
            // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部
            // 左闭右开，所以判断循环结束时， j != startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列
            // 左闭右开，所以判断循环结束时， i != startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        return nums;
    }

    // 测试生成螺旋矩阵
    public static void main2(String[] args) {
        int[][] nums = generateMatrix(5);
        for (int[] num : nums) {
            System.out.println(Arrays.toString(num));
        }
    }

    // 58 区间和的暴力解法
    public static void main58(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int length = scanner.nextInt();
        int[] array = new int[length];
        int[] sum = new int[length];
        for (int i = 0; i < length; i++) {
            array[i] = scanner.nextInt();
            if (i == 0){
                sum[i] = array[i];
            }else {
                sum[i] = sum[i-1] + array[i];
            }
        }
        while (scanner.hasNextInt()){
            int left = scanner.nextInt();
            int right = scanner.nextInt();
            int res;
            if (left == 0){
                res = sum[right];
            }else {
                res = sum[right] - sum[left - 1];
            }
            System.out.println(res);
        }
        scanner.close();
    }
    //44. 开发商购买土地
    public static void main44(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] array = new int[n][m];
        int[] hang = new int[n];
        int[] lie = new int[m];
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                array[i][j] = scanner.nextInt();
                sum += array[i][j];
                hang[i] += array[i][j];
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                lie[i] += array[j][i];
            }
        }
        int res = Integer.MAX_VALUE;
        int temp = 0;
        int result;
        for (int i = 0; i < n; i++) {
            temp += hang[i];
            result = Math.abs((sum-temp) - temp);
            if (result<res)
                res = result;
        }
        temp = 0;
        for (int j = 0; j < m; j++) {
            temp += lie[j];
            result = Math.abs((sum-temp) - temp);
            if (result<res)
                res = result;
        }
        System.out.println(res);
    }
    //优化
    public static void main44_2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int sum = 0;
        int[][] vec = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                vec[i][j] = scanner.nextInt();
                sum += vec[i][j];
            }
        }

        int result = Integer.MAX_VALUE;
        int count = 0; // 统计遍历过的行

        // 行切分
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                count += vec[i][j];
                // 遍历到行末尾时候开始统计
                if (j == m - 1) {
                    result = Math.min(result, Math.abs(sum - 2 * count));
                }
            }
        }
        count = 0;
        // 列切分
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                count += vec[i][j];
                // 遍历到列末尾时候开始统计
                if (i == n - 1) {
                    result = Math.min(result, Math.abs(sum - 2 * count));
                }
            }
        }
        System.out.println(result);
        scanner.close();
    }
    // 203
    public ListNode removeElements(ListNode head, int val) {
        ListNode listNode = new ListNode(0, head);
        ListNode node = listNode;
        while (node.next != null){
            if (node.next.val == val){
                node.next = node.next.next;
            }else {
                node = node.next;
            }
        }
        return listNode.next;
    }
    // 707
//单链表
    class MyLinkedList {
        class ListNode {
            int val;
            ListNode next;
            ListNode(int val) {
                this.val=val;
            }
        }
        //size存储链表元素的个数
        private int size;
        //注意这里记录的是虚拟头结点
        private ListNode head;
        //初始化链表
        public MyLinkedList() {
            this.size = 0;
            this.head = new ListNode(0);
        }

        //获取第index个节点的数值，注意index是从0开始的，第0个节点就是虚拟头结点
        public int get(int index) {
            //如果index非法，返回-1
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode cur = head;
            //第0个节点是虚拟头节点，所以查找第 index+1 个节点
            for (int i = 0; i <= index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }

        public void addAtHead(int val) {
            ListNode newNode = new ListNode(val);
            newNode.next = head.next;
            head.next = newNode;
            size++;

            // 在链表最前面插入一个节点，等价于在第0个元素前添加
            // addAtIndex(0, val);
        }

        public void addAtTail(int val) {
            ListNode newNode = new ListNode(val);
            ListNode cur = head;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = newNode;
            size++;

            // 在链表的最后插入一个节点，等价于在(末尾+1)个元素前添加
            // addAtIndex(size, val);
        }

        // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
        // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
        // 如果 index 大于链表的长度，则返回空
        public void addAtIndex(int index, int val) {
            if (index < 0 || index > size) {
                return;
            }

            //找到要插入节点的前驱
            ListNode pre = head;
            for (int i = 0; i < index; i++) {
                pre = pre.next;
            }
            ListNode newNode = new ListNode(val);
            newNode.next = pre.next;
            pre.next = newNode;
            size++;
        }

        public void deleteAtIndex(int index) {
            if (index < 0 || index >= size) {
                return;
            }

            //因为有虚拟头节点，所以不用对index=0的情况进行特殊处理
            ListNode pre = head;
            for (int i = 0; i < index ; i++) {
                pre = pre.next;
            }
            pre.next = pre.next.next;
            size--;
        }
    }
    //206 双链表法
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
    // 24 两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1);
        dumyhead.next = head;
        ListNode cur = dumyhead;
        ListNode first;
        ListNode second;
        while (cur.next != null && cur.next.next != null){
            first = cur.next;
            second = first.next;

            cur.next = second;
            first.next = second.next;
            second.next=first;
            cur = first;
        }
        return dumyhead.next;
    }
    // 19 删除链表的倒数第N个节点
    // 解题思路：双指针，要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点。
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //新建一个虚拟头节点指向head
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;
        //快慢指针指向虚拟头节点
        ListNode fastIndex = dummyNode;
        ListNode slowIndex = dummyNode;

        // 只要快慢指针相差 n 个结点即可
        for (int i = 0; i <= n; i++) {
            fastIndex = fastIndex.next;
        }
        while (fastIndex != null) {
            fastIndex = fastIndex.next;
            slowIndex = slowIndex.next;
        }

        // 检查 slowIndex.next 是否为 null，以避免空指针异常
        if (slowIndex.next != null) {
            slowIndex.next = slowIndex.next.next;
        }
        return dummyNode.next;
    }
    // 02.07 链表相交
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> visited = new HashSet<ListNode>();
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null) {
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
    // 方法二，双指针法  a+c=m，b+c=n。则a+c+b = b+c+a
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA, pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
    // 方法三
    //先行移动长链表实现同步移动
    public ListNode getIntersectionNode3(ListNode headA, ListNode headB) {
        ListNode curA = headA;
        ListNode curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != null) { // 求链表A的长度
            lenA++;
            curA = curA.next;
        }
        while (curB != null) { // 求链表B的长度
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        // 让curA为最长链表的头，lenA为其长度
        if (lenB > lenA) {
            //1. swap (lenA, lenB);
            int tmpLen = lenA;
            lenA = lenB;
            lenB = tmpLen;
            //2. swap (curA, curB);
            ListNode tmpNode = curA;
            curA = curB;
            curB = tmpNode;
        }
        // 求长度差
        int gap = lenA - lenB;
        // 让curA和curB在同一起点上（末尾位置对齐）
        while (gap-- > 0) {
            curA = curA.next;
        }
        // 遍历curA 和 curB，遇到相同则直接返回
        while (curA != null) {
            if (curA == curB) {
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }

    //142 环形链表，哈希表法
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
    // 142 环形链表(方法二)
    // https://leetcode.cn/problems/linked-list-cycle-ii/solutions/12616/linked-list-cycle-ii-kuai-man-zhi-zhen-shuang-zhi-/
    public ListNode detectCycle2(ListNode head) {
        ListNode fast = head, slow = head;
        while (true) {
            if (fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
    // 242 有效的字母异位词
    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length())
            return false;
        int[] record = new int[26];
        for (int i = 0; i < s.length(); i++) {
            record[s.charAt(i) - 'a'] ++;
        }
        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i) - 'a'] --;
        }
        for (int i = 0; i < record.length; i++) {
            if (record[i] != 0){
                return false;
            }
        }
        return true;
    }
    //349. 两个数组的交集
    public int[] intersection(int[] nums1, int[] nums2) {
        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历数组1
        for (int i : nums1) {
            set1.add(i);
        }
        //遍历数组2的过程中判断哈希表中是否存在该元素
        for (int i : nums2) {
            if (set1.contains(i)) {
                resSet.add(i);
            }
        }
        // 创建一个 int[] 数组，大小为 Set 的大小
        int[] result = new int[resSet.size()];
        // 遍历 Set 并将元素填充到数组中
        int index = 0;
        for (Integer num : resSet) {
            result[index++] = num;
        }
        return result;
    }
    //349. 两个数组的交集
    // 方法二，定义整个范围，使用hash遍历
    public int[] intersection2(int[] nums1, int[] nums2) {
        int[] hashTable = new int[1001];
        List<Integer> resultList = new ArrayList<>();
        for(int nums : nums1) {
            hashTable[nums] = 1;
        }
        for (int num : nums2) {
            if (hashTable[num] == 1) {
                resultList.add(num);
                hashTable[num] = 0;
            }
        }
        // 将结果列表转换为数组并返回
        int[] resultArray = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            resultArray[i] = resultList.get(i);
        }
        return resultArray;
    }
    //349. 两个数组的交集
    // 方法三 删除Set重复的元素
    // 更简洁的写法见右边的【Java Stream】
    public int[] intersection3(int[] nums1, int[] nums2) {
        Set<Integer> st = new HashSet<>();
        for (int x : nums1) {
            st.add(x);
        }

        List<Integer> lst = new ArrayList<>();
        for (int x : nums2) {
            if (st.remove(x)) { // x 在 st 中
                lst.add(x);
            }
        }

        // 由于返回值是 int[]，需要额外遍历一次
        int[] ans = new int[lst.size()];
        for (int i = 0; i < lst.size(); i++) {
            ans[i] = lst.get(i);
        }
        return ans;
    }
    // 202 快乐数
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        String s;
        while (true) {
            s = String.valueOf(n);
            int res = 0;
            for (int i = 0; i < s.length(); i++) {
                res += (s.charAt(i) - '0') * (s.charAt(i) - '0');
            }
            if (record.contains(res)) {
                return false;
            }
            if (res == 1) {
                return true;
            }
            record.add(res);
            n = res;
        }
    }
    // 方法二
    // 202 快乐数
    public boolean isHappy2(int n) {
        Set<Integer> record = new HashSet<>();
        while (n != 1 && !record.contains(n)) {
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n) {
        int res = 0;
        while (n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n = n / 10;
        }
        return res;
    }
    // 1.两数之和
    public int[] twoSum(int[] nums, int target) {
        int[] sum = new int[2];
        if(nums == null || nums.length == 0){
            return sum;
        }
        HashMap<Integer,Integer> record = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (record.containsKey(target - nums[i])){
                sum[0] = i;
                sum[1] = record.get(target - nums[i]);
                break;
            }
            record.put(nums[i],i);
        }
        return sum;
    }
    // 454 四数相加 II
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int sum;
        int count = 0;
        for (int i : nums1){
            for (int j : nums2) {
                sum = i+j;
                map.put(sum,map.getOrDefault(sum,0)+1);
            }
        }
        for (int i : nums3){
            for (int j : nums4) {
                count += map.getOrDefault(0 - i - j, 0);
            }
        }
        return count;
    }
    // 方法二 用map的merge方法判断 新key是否存在，存在则对value操作
    // 454 四数相加 II
    public int fourSumCount2(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> cnt = new HashMap<>();
        for (int x : nums1) {
            for (int y : nums2) {
                cnt.merge(x + y, 1, Integer::sum); // cnt[x+y]++
            }
        }

        int ans = 0;
        for (int x : nums3) {
            for (int y : nums4) {
                ans += cnt.getOrDefault(-x - y, 0);
            }
        }
        return ans;
    }
    // 383 赎金信
    // map实现hash
    public boolean canConstruct(String ransomNote, String magazine) {
        // shortcut
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++) {
            map.put(magazine.charAt(i),map.getOrDefault(magazine.charAt(i),0)+1);
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if (map.containsKey(ransomNote.charAt(i)) && map.get(ransomNote.charAt(i)) > 0) {
                map.put(ransomNote.charAt(i),map.get(ransomNote.charAt(i))-1);
            }else {
                return false;
            }
        }
        return true;
    }
    // 方法二，数组实现hash表
    // 383 赎金信
    public boolean canConstruct2(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        // 定义一个哈希映射数组
        int[] record = new int[26];
        for(char c : magazine.toCharArray()){
            record[c - 'a'] += 1;
        }
        for(char c : ransomNote.toCharArray()){
            record[c - 'a'] -= 1;
        }
        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for(int i : record){
            if(i < 0){
                return false;
            }
        }
        return true;
    }
    // 15.三数之和 完美解法
    // 因为不能重复，所以需要去重
    // i的增加 影响 while (right > left)
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        // 找出a + b + c = 0
        // a = nums[i], b = nums[left], c = nums[right]
        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;

                    right--;
                    left++;
                }
            }
        }
        return result;
    }
    // 18.四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);  // 排序数组
        List<List<Integer>> result = new ArrayList<>();  // 结果集
        for (int k = 0; k < nums.length; k++) {
            // 剪枝处理
            if (nums[k] > target && nums[k] >= 0) {
                break;	// 此处的break可以等价于return result;
            }
            // 对nums[k]去重
            if (k > 0 && nums[k] == nums[k - 1]) {
                continue;
            }
            for (int i = k + 1; i < nums.length; i++) {
                // 第二级剪枝
                if (nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) {
                    break;	// 注意是break到上一级for循环，如果直接return result;会有遗漏
                }
                // 对nums[i]去重
                if (i > k + 1 && nums[i] == nums[i - 1]) {
                    continue;
                }
                int left = i + 1;
                int right = nums.length - 1;
                while (right > left) {
                    long sum = (long) nums[k] + nums[i] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[k], nums[i], nums[left], nums[right]));
                        // 对nums[left]和nums[right]去重
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
    // 方法二 究极优化
    // https://leetcode.cn/problems/4sum/solutions/2344514/ji-zhi-you-hua-ji-yu-san-shu-zhi-he-de-z-1f0b/
    public List<List<Integer>> fourSum2(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for (int a = 0; a < n - 3; a++) { // 枚举第一个数
            long x = nums[a]; // 使用 long 避免溢出
            if (a > 0 && x == nums[a - 1]) continue; // 跳过重复数字
            if (x + nums[a + 1] + nums[a + 2] + nums[a + 3] > target) break; // 优化一
            if (x + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue; // 优化二
            for (int b = a + 1; b < n - 2; b++) { // 枚举第二个数
                long y = nums[b];
                if (b > a + 1 && y == nums[b - 1]) continue; // 跳过重复数字
                if (x + y + nums[b + 1] + nums[b + 2] > target) break; // 优化一
                if (x + y + nums[n - 2] + nums[n - 1] < target) continue; // 优化二
                int c = b + 1;
                int d = n - 1;
                while (c < d) { // 双指针枚举第三个数和第四个数
                    long s = x + y + nums[c] + nums[d]; // 四数之和
                    if (s > target) d--;
                    else if (s < target) c++;
                    else { // s == target
                        ans.add(Arrays.asList((int)x, (int)y, nums[c], nums[d]));
                        for (c++; c < d && nums[c] == nums[c - 1]; c++) ; // 跳过重复数字
                        for (d--; d > c && nums[d] == nums[d + 1]; d--) ; // 跳过重复数字
                    }
                }
            }
        }
        return ans;
    }
    // 344 反转字符串
    public void reverseString(char[] s) {
        char temp;
        for (int i = 0,j = s.length-1; i < j; i++,j--) {
            temp = s[i];
            s[i] = s[j];
            s[j] = temp;
        }
    }
    // 541. 反转字符串II
    public String reverseStr(String s, int k) {
        int le = s.length();
        int offset = 0;
        char temp;
        char[] str = s.toCharArray();
        while (offset<le){
            if ((offset+2*k)<le){
                for (int i = offset,j = offset + k-1; i < j; i++,j--) {
                    temp = str[i];
                    str[i] = str[j];
                    str[j] = temp;
                }
                offset+=2*k;
                continue;
            } else if (le < k + offset) {
                for (int i = offset,j = le-1; i < j; i++,j--) {
                    temp = str[i];
                    str[i] = str[j];
                    str[j] = temp;
                }
                break;
            } else{
                for (int i = offset,j = offset+k-1; i < j; i++,j--) {
                    temp = str[i];
                    str[i] = str[j];
                    str[j] = temp;
                }
                break;
            }
        }
        String s1 = String.valueOf(str);
        return s1;
    }
    // 实际上就是把区间[nk,(n+1)k]的字符反转，但每次的偏移量是2*k，
    public String reverseStr2(String S, int k) {
        char[] s = S.toCharArray();
        int n = s.length;
        for (int i = 0; i < n; i += k * 2) {
            reverse(s, i, Math.min(i + k, n) - 1);
        }
        return new String(s);
    }

    private void reverse(char[] s, int left, int right) {
        while (left < right) {
            char tmp = s[left];
            s[left++] = s[right];
            s[right--] = tmp;
        }
    }

    //替换数字
    public static String replaceDigitsWithNumber(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                sb.append("number"); // 如果是数字字符，替换为 "number"
            } else {
                sb.append(c); // 如果是字母字符，保持不变
            }
        }
        return sb.toString();
    }
    //151 翻转字符串里的单词
    public String reverseWords(String s) {
        // 按空格分割字符串，得到单词数组
        String[] words = s.split(" ");
        StringBuilder reversed = new StringBuilder();

        // 从后向前遍历单词数组
        for (int i = words.length - 1; i >= 0; i--) {
            reversed.append(words[i]);
            if (i > 0) {
                reversed.append(" "); // 在单词之间添加空格
            }
        }

        return reversed.toString();
    }

    // 151 方法2 双指针
    public String reverseWords2(String s) {
        s = s.trim();                                    // 删除首尾空格
        int j = s.length() - 1, i = j;
        StringBuilder res = new StringBuilder();
        while (i >= 0) {
            while (i >= 0 && s.charAt(i) != ' ') i--;     // 搜索首个空格
            res.append(s.substring(i + 1, j + 1) + " "); // 添加单词
            while (i >= 0 && s.charAt(i) == ' ') i--;     // 跳过单词间空格
            j = i;                                       // j 指向下个单词的尾字符
        }
        return res.toString().trim();                    // 转化为字符串并返回
    }

    public String reverseWords3(String s) {
        StringBuilder sb=new StringBuilder();
        if(s==null||s.length()<=0)
            return "";
        int endLeft=s.length()-1;
        int endRight=s.length()-1;
        while(endLeft>=0&&endRight>=0){
            while (endRight>=0&&s.charAt(endRight)==' '){
                endRight--;
            }
            endLeft=endRight;
            while (endLeft>=0&&s.charAt(endLeft)!=' '){
                endLeft--;
            }
            if(endLeft!=endRight){
                sb.append(s.substring(endLeft+1,endRight+1)).append(" ");
            }
            endRight=endLeft;
            sb.toString().indexOf("abc");
        }
        if(sb.length()>0)
            sb.deleteCharAt(sb.length()-1);
        return sb.toString();
    }
    // 28 实现 strStr()


    // 459 重复的子字符串
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        for (int i = 1; i * 2 <= n; ++i) {
            // 保证整除
            if (n % i == 0) {
                boolean match = true;
                for (int j = i; j < n; ++j) {
                    if (s.charAt(j) != s.charAt(j - i)) {
                        match = false;
                        break;
                    }
                }
                if (match) {
                    return true;
                }
            }
        }
        return false;

    }
    // 232
    class MyQueue {
        Stack<Integer> stackIn;
        Stack<Integer> stackOut;
        public MyQueue() {
            stackIn = new Stack<>();
            stackOut = new Stack<>();
        }

        public void push(int x) {
            stackIn.push(x);
        }

        public int pop() {
            if (!stackOut.isEmpty())
                return stackOut.pop();
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
            return stackOut.pop();
        }

        public int peek() {
            if (!stackOut.isEmpty())
                return stackOut.peek();
            while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
            }
            return stackOut.peek();
        }

        public boolean empty() {
            if (!stackOut.isEmpty())
                return false;
            if (stackIn.isEmpty())
                return true;
            return false;
        }
    }
    // 225
    class MyStack {
        Queue<Integer> queue;

        public MyStack() {
            queue = new LinkedList<>();
        }

        public void push(int x) {
            queue.add(x);
        }

        public int pop() {
            rePosition();
            return queue.poll();
        }

        public int top() {
            rePosition();
            int result = queue.poll();
            queue.add(result);
            return result;
        }

        public boolean empty() {
            return queue.isEmpty();
        }

        public void rePosition(){
            int size = queue.size();
            size--;
            while(size-->0)
                queue.add(queue.poll());
        }
    }
    // 225
    class MyStack2 {

        Queue<Integer> queue;

        public MyStack2() {
            queue = new LinkedList<>();
        }

        //每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
        public void push(int x) {
            queue.offer(x);
            int size = queue.size();
            //移动除了 A 的其它数
            while (size-- > 1)
                queue.offer(queue.poll());
        }

        public int pop() {
            return queue.poll();
        }

        public int top() {
            return queue.peek();
        }

        public boolean empty() {
            return queue.isEmpty();
        }
    }
    // 20
    public boolean isValid(String s) {
        Deque<Character> deque = new LinkedList<>();
        char ch;
        for (int i = 0; i < s.length(); i++) {
            ch = s.charAt(i);
            //碰到左括号，就把相应的右括号入栈
            if (ch == '(') {
                deque.push(')');
            }else if (ch == '{') {
                deque.push('}');
            }else if (ch == '[') {
                deque.push(']');
            } else if (deque.isEmpty() || deque.peek() != ch) {
                return false;
            }else {//如果是右括号判断是否和栈顶元素匹配
                deque.pop();
            }
        }
        //遍历结束，如果栈为空，则括号全部匹配
        return deque.isEmpty();
    }
    // 1047
    public String removeDuplicates(String s) {
        // 将 res 当做栈
        // 也可以用 StringBuilder 来修改字符串，速度更快
        // StringBuilder res = new StringBuilder();
        StringBuffer res = new StringBuffer();
        // top为 res 的长度
        int top = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // 当 top >= 0,即栈中有字符时，当前字符如果和栈中字符相等，弹出栈顶字符，同时 top--
            if (top >= 0 && res.charAt(top) == c) {
                res.deleteCharAt(top);
                top--;
                // 否则，将该字符 入栈，同时top++
            } else {
                res.append(c);
                top++;
            }
        }
        return res.toString();
    }
    // 150
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for (String s : tokens) {
            if ("+".equals(s)) {        // leetcode 内置jdk的问题，不能使用==判断字符串是否相等
                stack.push(stack.pop() + stack.pop());      // 注意 - 和/ 需要特殊处理
            } else if ("-".equals(s)) {
                stack.push(-stack.pop() + stack.pop());
            } else if ("*".equals(s)) {
                stack.push(stack.pop() * stack.pop());
            } else if ("/".equals(s)) {
                int temp1 = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2 / temp1);
            } else {
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
    // 239
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        for(int j = 0, i = 1 - k; j < nums.length; i++, j++) {
            // 删除 deque 中对应的 nums[i-1]
            if(i > 0 && deque.peekFirst() == nums[i - 1])
                deque.removeFirst();
            // 保持 deque 递减
            while(!deque.isEmpty() && deque.peekLast() < nums[j])
                deque.removeLast();
            deque.addLast(nums[j]);
            // 记录窗口最大值
            if(i >= 0)
                res[i] = deque.peekFirst();
        }
        return res;
    }

    //  “未形成窗口” 和 “形成窗口后” 两个阶段拆分到两个循环里实现。代码虽变长，但减少了冗余的判断操作。
    public int[] maxSlidingWindow2(int[] nums, int k) {
        if(nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] res = new int[nums.length - k + 1];
        // 未形成窗口
        for(int i = 0; i < k; i++) {
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
        }
        res[0] = deque.peekFirst();
        // 形成窗口后
        for(int i = k; i < nums.length; i++) {
            if(deque.peekFirst() == nums[i - k])
                deque.removeFirst();
            while(!deque.isEmpty() && deque.peekLast() < nums[i])
                deque.removeLast();
            deque.addLast(nums[i]);
            res[i - k + 1] = deque.peekFirst();
        }
        return res;
    }
    // 155
    class MinStack {
        Stack<Integer> stack;
        Stack<Integer> mStack;

        public MinStack() {
            stack = new Stack<Integer>();
            mStack = new Stack<Integer>();
        }

        public void push(int val) {
            stack.push(val);
            if (mStack.isEmpty()) {
                mStack.push(val);
                return;
            }
            if (mStack.peek()>=val){
                mStack.push(val);
            }
        }

        public void pop() {
            if (stack.peek().equals(mStack.peek())){
                mStack.pop();
                stack.pop();
                return;
            }
            stack.pop();
        }

        public int top() {
            return stack.peek();
        }

        public int getMin() {
            return mStack.peek();
        }
    }
    // 155方法二
    /*
    * class MinStack {
    private ListNode head;

    public MinStack() {
    }

    public void push(int x) {
        if (isEmpty()) {
            head = new ListNode(x, x, null); // 如果栈为空，直接创建一个新节点
        } else {
            head = new ListNode(x, Math.min(x, head.min), head); // 新节点的最小值是当前值和上一个最小值的较小值
        }
    }

    public void pop() {
 if        (isEmpty()) {
            throw new IllegalStateException("Stack is empty...");
        }
        head = head.next; // 移动到下一个节点
    }

    public int top() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty...");
        }
        return head.val; // 返回当前节点的值
    }

    public int getMin() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty...");
        }
        return head.min; // 返回当前节点记录的最小值
    }

    public boolean isEmpty() {
        return head == null; // 检查链表是否为空
    }
}

class ListNode {
    public int val; // 当前节点的值
    public int min; // 当前栈的最小值
    public ListNode next; // 指向下一个节点

    public ListNode(int val, int min, ListNode next) {
        this.val = val;
        this.min = min;
        this.next = next;
    }
}
    * */
    // 347
    //解法1：基于大顶堆实现
    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num,0) + 1);
        }
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair2[1] - pair1[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {//大顶堆需要对所有元素进行排序
            pq.add(new int[]{entry.getKey(), entry.getValue()});
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) { //依次从队头弹出k个,就是出现频率前k高的元素
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
    //解法2：基于小顶堆实现
    public int[] topKFrequent2(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>(); //key为数组元素值,val为对应出现次数
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数
        //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆)
        PriorityQueue<int[]> pq = new PriorityQueue<>((pair1, pair2) -> pair1[1] - pair2[1]);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) { //小顶堆只需要维持k个元素有序
            if (pq.size() < k) { //小顶堆元素个数小于k个时直接加
                pq.add(new int[]{entry.getKey(), entry.getValue()});
            } else {
                if (entry.getValue() > pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个)
                    pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了
                    pq.add(new int[]{entry.getKey(), entry.getValue()});
                }
            }
        }
        int[] ans = new int[k];
        for (int i = k - 1; i >= 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多
            ans[i] = pq.poll()[0];
        }
        return ans;
    }



    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    // 前序
    public List<Integer> preorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        preorder(root,list);
        return list;
    }
    void preorder(TreeNode root,ArrayList<Integer> list){
        if (root == null){
            return;
        }
        list.add(root.val);
        preorder(root.left,list);
        preorder(root.right,list);
    }
    // 中序
    public List<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        inorder(root,list);
        return list;
    }
    void inorder(TreeNode root,ArrayList<Integer> list){
        if (root == null){
            return;
        }
        inorder(root.left,list);
        list.add(root.val);
        inorder(root.right,list);
    }
    // 倒序
    public List<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        postorder(root,list);
        return list;
    }
    void postorder(TreeNode root,ArrayList<Integer> list) {
        if (root == null) {
            return;
        }
        postorder(root.left, list);
        postorder(root.right, list);
        list.add(root.val);
    }
    // 迭代法
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null){
                stack.push(node.right);
            }
            if (node.left != null){
                stack.push(node.left);
            }
        }
        return result;
    }
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (!stack.isEmpty() || cur != null){
            if (cur != null){
                stack.push(cur);
                cur =cur.left;
            }else {
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }
        return result;
    }
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        if (root == null)
            return list;
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addFirst(root);
        while (!deque.isEmpty()){
            ArrayList<Integer> cur = new ArrayList<>();
            int size = deque.size();
            for (int i = 1;i<=size;i++){
                TreeNode node = deque.removeFirst();
                cur.add(node.val);
                if (node.left != null) {
                    deque.addLast(node.left);
                }
                if (node.right != null) {
                    deque.addLast(node.right);
                }
            }
            list.add(cur);
        }
        return list;
    }
    //226 采用前序遍历
    public TreeNode invertTree(TreeNode root) {
        TreeNode cur = root;
        invert(cur);
        return root;
    }
    void invert(TreeNode cur){
        if (cur == null){
            return;
        }
        TreeNode temp;
        temp = cur.left;
        cur.left = cur.right;
        cur.right = temp;
        invert(cur.left);
        invert(cur.right);
    }
    class Node {
        public int val;
        public List<Node> children;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, List<Node> _children) {
            val = _val;
            children = _children;
        }
    }
    // 589
    public List<Integer> preorder(Node root) {
        ArrayList<Integer> list = new ArrayList<>();
        pre(root,list);
        return list;
    }

    private void pre(Node root, ArrayList<Integer> list) {
        if (root == null){
            return;
        }
        list.add(root.val);
        for(Node node : root.children){
            pre(node,list);
        }
    }
    // 105
    private Map<Integer, Integer> indexMap;
    public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right) {
            return null;
        }
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);

        // 先把根节点建立出来
        TreeNode root = new TreeNode(preorder[preorder_root]);
        // 得到左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = preorder.length;
        // 构造哈希映射，帮助我们快速定位根节点
        indexMap = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            indexMap.put(inorder[i], i);
        }
        return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);
    }
    // 101
    public boolean isSymmetric(TreeNode root) {
        return root == null || recur(root.left, root.right);
    }
    boolean recur(TreeNode L, TreeNode R) {
        if (L == null && R == null) return true;
        if (L == null || R == null || L.val != R.val) return false;
        return recur(L.left, R.right) && recur(L.right, R.left);
    }
    // 方法二
    public boolean isSymmetric2(TreeNode root) {
        return check(root, root);
    }

    public boolean check(TreeNode u, TreeNode v) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(u);
        q.offer(v);
        while (!q.isEmpty()) {
            u = q.poll();
            v = q.poll();
            if (u == null && v == null) {
                continue;
            }
            if ((u == null || v == null) || (u.val != v.val)) {
                return false;
            }

            q.offer(u.left);
            q.offer(v.right);

            q.offer(u.right);
            q.offer(v.left);
        }
        return true;
    }
    // 617 使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if (t1 == null) {
            return t2;
        }
        if (t2 == null) {
            return t1;
        }
        TreeNode merged = new TreeNode(t1.val + t2.val);
        merged.left = mergeTrees(t1.left, t2.left);
        merged.right = mergeTrees(t1.right, t2.right);
        return merged;
    }
    // 105
    private Map<Integer, Integer> position;
    public TreeNode buildTree1(int[] preorder, int[] inorder) {
        position = new HashMap<Integer,Integer>();
        int n = inorder.length;
        for (int i = 0; i < n; i++) {
            position.put(inorder[i],i);
        }
        return mBuildTree(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode mBuildTree(int[] preorder, int[] inorder, int pre_left, int pre_right, int ino_left, int ino_right) {
        if (pre_left>pre_right)
            return null;
        int pre_root = pre_left;
        int inr_root = position.get(preorder[pre_root]);
        int size = inr_root - ino_left;
        TreeNode node = new TreeNode(preorder[pre_root]);
        node.left = mBuildTree(preorder,inorder,pre_root + 1,pre_left + size,ino_left,inr_root-1);
        node.right = mBuildTree(preorder,inorder,pre_left+size+1,pre_right,inr_root+1,ino_right);
        return node;
    }
    private TreeNode ans;

    public Solution() {
        this.ans = null;
    }

    private boolean dfs(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return false;
        boolean lson = dfs(root.left, p, q);
        boolean rson = dfs(root.right, p, q);
        if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root.val == p.val || root.val == q.val);
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        this.dfs(root, p, q);
        return this.ans;
    }

    // 哈希表实现
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        // 层序遍历
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.addFirst(root);
        while (!deque.isEmpty()){
            int size = deque.size();
            for (int i = 0; i < size; i++) {
                TreeNode treeNode = deque.removeFirst();
                if (treeNode.left!=null) deque.addFirst(treeNode.left);
                if (treeNode.right!=null) deque.addFirst(treeNode.right);
                map.put(treeNode.left,treeNode);
                map.put(treeNode.right,treeNode);
            }
        }
        // 找p的所有祖先
        ArrayList<TreeNode> list1 = new ArrayList<>();
        TreeNode cur = p;
        while (cur != null){
            list1.add(cur);
            cur = map.get(cur);
        }
        cur = q;
        while (!list1.contains(cur)){
            cur = map.get(cur);
        }
        return cur;
    }
    // 方法三
    Map<Integer, TreeNode> parent = new HashMap<Integer, TreeNode>();
    Set<Integer> visited = new HashSet<Integer>();

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
    // 236
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }
    // 338
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int temp = i;
            int count = 0;
            while (temp!=0){
                if (temp%2==1)
                    count++;
                temp = temp/2;
            }
            res[i] = count;
        }
        return res;
    }
    // better
    public int[] countBits2(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            int count = 0;
            int num = i;
            while (num != 0) {
                count += num & 1;
                num >>>= 1;
            }
            res[i] = count;
        }
        return res;
    }
    // 234
    public boolean isPalindrome(ListNode head) {
        ArrayList<Integer> list = new ArrayList<>();
        while (head!=null){
            list.add(head.val);
            head= head.next;
        }
        int size = list.size();
        for (int i = 0; i < size/2; i++) {
            if (list.get(i) != list.get(size-i-1))
                return false;
        }
        return true;
    }
    // 双指针 两个for循环 暴力
    public int[] dailyTemperatures(int[] temperatures) {
        int length = temperatures.length;
        int[] res = new int[length];
        res[length -1] = 0;
        int temp = 0;
        while (temp <length -1){
            int left = temp;
            int right = temp + 1;
            while (right != length && temperatures[left]>temperatures[right]) {
                right++;
            }
            if (right == length) {
                res[temp] = 0;
                continue;
            }

            res[temp] = right-left;
            temp++;
        }
        return res;
    }
    // 单调栈，存放的是单调数组
    public int[] dailyTemperatures2(int[] temperatures) {
        int length = temperatures.length;
        int[] res = new int[length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < length; i++) {
            if (stack.isEmpty() || temperatures[stack.peek()] >= temperatures[i]){
                stack.push(i);
            }else{
                while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]){
                    int pop = stack.pop();
                    res[pop] = i - pop;
                }
                stack.push(i);
            }
        }
        while (!stack.isEmpty()){
            int pop = stack.pop();
            res[pop] = 0;
        }
        return res;

/*        int len = temperatures.length;
        int[] rs = new int[len];
        Deque<Integer> idxStack = new LinkedList<>();
        for (int i = 0 ; i < len; i++) {
            while(!idxStack.isEmpty() && temperatures[idxStack.peek()] < temperatures[i]) {
                int curIdx = idxStack.pop();
                rs[curIdx] = i - curIdx;
            }
            idxStack.push(i);
        }
        return rs;
    }*/
    }
    //215
    public int findKthLargest(int[] nums, int k) {
        int res = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>((pair1, pair2) -> pair2 - pair1);
        for (int i = 0; i < nums.length; i++) {
            pq.add(nums[i]);
        }
        for (int i = 1; i <= k; i++) {
            res = pq.poll();
        }
        return res;
    }
    // 21
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        if (list1 !=null)
            cur.next = list1;
        if (list2 !=null)
            cur.next = list2;
        return dummy.next;
    }
    // 方法二，迭代法 使用递归
    public ListNode mergeTwoLists2(ListNode list1, ListNode list2) {
        if(list1 == null) {
            return list2;
        }
        if(list2 == null) {
            return list1;
        }

        if(list1.val < list2.val) {
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
    // 70 动态规划
    public int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q;
            q = r;
            r = p + q;
        }
        return r;
    }
    // 104 广度优先遍历
    public int maxDepth(TreeNode root) {
        if (root==null)
            return 0;
        int count = 1;
        ArrayDeque<TreeNode> nodes = new ArrayDeque<>();
        nodes.addFirst(root);
        while (!nodes.isEmpty()){
            int size = nodes.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = nodes.removeLast();
                if (node.left!=null) nodes.addFirst(node.left);
                if (node.right!=null) nodes.addFirst(node.right);
            }
            if (!nodes.isEmpty())
                count++;
        }
        return count;
    }
    // 深度优先遍历
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            int leftHeight = maxDepth2(root.left);
            int rightHeight = maxDepth2(root.right);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

